home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / quartz / quartz10.lha / src / presto / parallel.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-02  |  6.7 KB  |  221 lines
  1. /* $Copyright:    $
  2.  * Copyright (c) 1984, 1985, 1986 Sequent Computer Systems, Inc.
  3.  * All rights reserved
  4.  *  
  5.  * This software is furnished under a license and may be used
  6.  * only in accordance with the terms of that license and with the
  7.  * inclusion of the above copyright notice.   This software may not
  8.  * be provided or otherwise made available to, or used by, any
  9.  * other person.  No title to or ownership of the software is
  10.  * hereby transferred.
  11.  */
  12.  
  13. /* $Header: /crg2/bruces2/rbk/C++/Presto/src/RCS/parallel.h,v 1.2 88/03/24 09:52:47 rbk Exp $
  14.  *
  15.  * parallel.h
  16.  *    Definitions for use in parallel, shared-memory programs.
  17.  */
  18.  
  19. /* $Log:    parallel.h,v $
  20.  *
  21.  * 90/01/14 jef
  22.  * HC_Spinlock fails sporadically when 16 processors are contending for a
  23.  * lock.  Visual inspection of code in hc_slock_asm.h SEEMS to indicate an
  24.  * 'off-by-1' problem - the private lock data is in x [procid][16] in an
  25.  * array indexed [p][16] (i.e., the private lock data is *ACTUALLY* dealt
  26.  * with in x [procid +1 ][0]!!).  Everything would still work fine, except
  27.  * for processor 16, whose private data would be found one byte off the end
  28.  * of the array (and when that byte changes value, processor 16 gets the
  29.  * lock, even if it shouldn't have!).  Modifying the hc_slock_t structure
  30.  * to be [procs][17] seems to solve the problem - however, the real
  31.  * problem is in the code and/or comments in hc_slock_asm.h.
  32.  *
  33.  * 89/12/28 jef
  34.  * Add support for a second type of spinlock which works well in
  35.  * high lock contention situations (after original by raj).
  36.  *
  37.  * Revision 1.2  88/03/24  09:52:47  rbk
  38.  * #ifdef ns32000 around ALM fuss.  Can't use system version of this file
  39.  * since C++ doesn't understand asm-functions yet.
  40.  * 
  41.  * Revision 1.1  88/03/22  15:26:42  rbk
  42.  * Initial revision
  43.  * 
  44.  */
  45.  
  46. #ifndef parallel_h
  47. #define parallel_h
  48.  
  49. /*
  50.  *  Number of processors supported by PRESTO.
  51.  */
  52. #define NUMPROCS 16
  53.  
  54. /*
  55.  *  Data structure for regular spinlock.
  56.  *  A "lock" is a byte of memory, initialized to zero (unlocked).
  57.  */
  58. typedef unsigned char    slock_t;
  59.  
  60. #ifdef i386
  61. /*
  62.  *  Data structure for high-contention spinlock based on queueing.
  63.  *
  64.  *  In a regular spinlock, all threads requesting the lock spin, performing
  65.  *  test-and-set operations on a single shared memory location.  The
  66.  *  resulting cache invalidation traffic quickly saturates the bus with
  67.  *  only a small number of spinning processors, impacting the performance
  68.  *  of the thread holding the lock (by interfering with it's ability to
  69.  *  access memory) and causing a rapid falloff in performance.
  70.  *
  71.  *  The queue-based spinlock is designed to eliminate this problem.  Threads
  72.  *  spin on a private location instead of a shared location, eliminating the
  73.  *  cache invalidation traffic.  To release a lock, the thread holding the
  74.  *  lock simply sets the private location that the next waiter is spinning on
  75.  *  (in this case no atomic instruction is needed).
  76.  *
  77.  *  Since a spinning thread does not relinquish it's processor, the
  78.  *  lock data structure need only support NUMPROCS threads.  In this
  79.  *  implementation, the DYNIX process id (from getpid ()) of the requesting
  80.  *  thread is used to index into the lock data structure.  Processor ids
  81.  *  are converted to range from 1 to NUMPROCS (as opposed to 0 to NUMPROCS-1
  82.  *  as in PRESTO).  Row 0 of the array is reserved for use in indicating the
  83.  *  identity of the last requestor of the lock.  It also stores a copy of
  84.  *  the last requestor's private data area.
  85.  *
  86.  *  The private location which each processor spins on while it waits to
  87.  *  acquire the lock is (supposedly) located at x [last_procid] [15], i.e.,
  88.  *  it spins on the private location of the last processor which requested
  89.  *  the lock (NOTE:  from the code in hc_slock_asm.h, I believe this
  90.  *  location is ACTUALLY x [last_procid] [*16*], which is why I increased
  91.  *  the length of each row to 17 (jef)).  I believe that the extra
  92.  *  15 bytes in each row are used to force each private location into a
  93.  *  separate cache line on the 386, thus eliminating extra cache coherency
  94.  *  traffic when a private location is set by a releasing lock holder.
  95.  *
  96.  *  See comments in hc_slock_asm.h for more details.
  97.  */
  98.  
  99. #define HC_S_LOCK_SIZE (NUMPROCS+1)
  100. typedef struct hc_slock_t { unsigned char x[HC_S_LOCK_SIZE][17]; };
  101.  
  102. #endif 386
  103.  
  104. #define    L_UNLOCKED    0
  105. #define    L_LOCKED    1
  106.  
  107. /*
  108.  * Was a conditional lock request granted (L_SUCCESS) or denied (L_FAILED)
  109.  */
  110. #define L_FAILED    0
  111. #define L_SUCCESS    1
  112.  
  113. /*
  114.  * A "barrier" allows multiple processes to synchronize by having
  115.  * all of them exit the barrier construct simultaneously.
  116.  *
  117.  * This version assumes <= 255 processes, fits in one 4-byte integer,
  118.  * and is based on spin-locks.
  119.  */
  120.  
  121. typedef struct    {
  122.     slock_t        b_mutex;    /* mutual exclusion */
  123.     unsigned char    b_limit;    /* number participants */
  124.     unsigned char    b_count;    /* state counter */
  125.     unsigned char    b_useno;    /* current use # (state flag) */
  126. } sbarrier_t;                /* 's' for "spin"-barrier */
  127.  
  128.  
  129. #ifndef c_plusplus
  130. /*
  131.  * Other useful declarations.
  132.  */
  133.  
  134. extern    char    *sbrk(), *shsbrk();
  135. extern    char    *shmalloc();
  136.  
  137. #endif
  138.  
  139. #ifdef    ns32000
  140. /*
  141.  * ALM_HASH() is used to hash an address to an ALM offset.
  142.  */
  143.  
  144. #define    ALM_HASH(x)    ((int)(&(x)) & (0xFF << 2))
  145.  
  146. /*
  147.  * S_LOCK() and S_UNLOCK() provide in-line access to locks for C-programs;
  148.  * these can be used in time-criticial situations, at a cost in code size.
  149.  *
  150.  * CAREFUL using S_LOCK(): cc -O -i doesn't do S_LOCK(&x) correctly; need
  151.  * to pass pointer to lock, not address of lock.
  152.  */
  153.  
  154. #define    S_LOCK(lp)    { \
  155.     register char    *lock_alm = &_alm_base[ALM_HASH(*(lp))]; \
  156.     for (;;) { \
  157.         /* Wait for lock to be available */ \
  158.         while (*(lp) == L_LOCKED) \
  159.             continue; \
  160.         /* Grab ALM gate for atomic access to lock */ \
  161.         while (*lock_alm & ALM_LOCKED) \
  162.             continue; \
  163.         /* Can race with others trying to get the lock */ \
  164.         if (*(lp) == L_UNLOCKED) { \
  165.             /* No race (or won it) -- grab the lock */ \
  166.             *(lp) = L_LOCKED; \
  167.             *lock_alm = ALM_UNLOCKED; \
  168.             break; \
  169.         } \
  170.         /* Lost race, try again */ \
  171.         *lock_alm = ALM_UNLOCKED; \
  172.     } \
  173. }
  174.  
  175. #define    S_UNLOCK(lp)    (*(lp) = L_UNLOCKED)
  176.  
  177. /*
  178.  * Various implementation dependent parameters.
  179.  */
  180.  
  181. #define    NBALM        4        /* number bytes per ALM */
  182. #define    ALMSIZE        1024        /* size of our portion of ALMs */
  183.  
  184. #define    ALM_UNLOCKED    0
  185. #define    ALM_LOCKED    1
  186.  
  187. #define    NALMDEVS    64        /* # different ALM's to try for */
  188.  
  189. #define    ADDR_RND    0x800        /* boundary round (text/data/end) */
  190.  
  191. #endif    ns32000
  192.  
  193. /*
  194.  * Convenience definitions.
  195.  */
  196.  
  197. #ifndef    NULL
  198. #define    NULL        0
  199. #endif
  200.  
  201. /*
  202.  * Various globally used data.
  203.  */
  204.  
  205. extern    int    errno;
  206.  
  207. extern    int    _shm_fd;        /* fd for shared data mapped file */
  208. #ifdef    ns32000
  209. extern    char    *_alm_base;        /* virt addr of mapped ALM's */
  210. #endif    ns32000
  211. extern    int    _pgoff;            /* getpagesize() - 1 */
  212.  
  213. /*
  214.  * PGRND() rounds up a value to next page boundary.
  215.  */
  216.  
  217. #define    PGRND(x)    (char *) (((int)(x) + _pgoff) & ~_pgoff)
  218.  
  219.  
  220. #endif parallel_h
  221.